package Sort;
/*
* 插入排序
* 3.1 算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
（1）从第一个元素开始，该元素可以认为已经被排序；

（2）取出下一个元素，在已经排序的元素序列中从后向前扫描；

（3）如果该元素（已排序）大于新元素，将该元素移到下一位置；

（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

（5）将新元素插入到该位置后；

（6）重复步骤2~5。
最好时间复杂度为O(n)，最坏时间复杂度为O(n^2)，平均时间复杂度为O(n^2)。 插入算法是稳定的排序算法。
* */
public class InsertionSort {

    static void insert(int[] nums){
        //当数组长度大于2时才有意义
        if(nums.length>=2){
            for (int i=1;i< nums.length;i++){
                //每次从未排序的数组中取第一个元素向前找应该在的位置，移动过程中交换位置。
                int preIndex = i-1;
                int curIndex = i;
                //当前一个元素的坐标不越界且前一个元素的值大于当前值，当前值和它交换
                while(preIndex>=0 && nums[preIndex] > nums[curIndex]){
                    int temp = nums[curIndex];
                    nums[curIndex] = nums[preIndex];
                    nums[preIndex] = temp;
                    preIndex--;
                    curIndex--;
                }
            }
        }

    }

    //2、插入排序
    static void insertSort(int[] a){
        int len=a.length;

        for(int i=1;i<len;++i){
            int current=a[i];
            int j=i-1;
            //查找需要插入的位置
            for(;j>=0 && a[j]>current;--j){
                a[j+1]=a[j];
            }
            a[j+1]=current;//插入数据
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,4,1,2,9,3,4,5};
        insertSort(nums);
        for (int i:nums
        ) {
            System.out.println(i);
        }
    }

}
